#include <bits/stdc++.h>
using namespace std;

class Solution
{
  private:
    vector<int> list;

    // 二分查找法，用于找到插入位置，保持list有序
    int binarySearch(int value)
    {
        if (list.empty())
            return 0;
        int left = 0;
        int right = list.size();

        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (list[mid] >= value)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right;
    }

  public:
    // 插入元素到list中，使用二分查找找到合适的位置以保持list有序
    void Insert(int num)
    {
        int index = binarySearch(num);
        list.insert(list.begin() + index, num);
    }

    // 获取list的中位数，如果list为空返回0.0
    double GetMedian()
    {
        if (list.empty())
            return 0.0;
        size_t size = list.size();

        if (size % 2 == 0)
        {
            return (list[size / 2 - 1] + list[size / 2]) / 2.0;
        }
        else
        {
            return static_cast<double>(list[size / 2]);
        }
    }
};

class Solution
{
  private:
    vector<int> list;
    int Search(int num)
    {
        if (list.empty())
            return 0;
        int l = 0;
        int r = list.size();
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (list[mid] >= num)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return r;
    }

  public:
    void Insert(int num)
    {
        int index = Search(num);
        list.insert(list.begin() + index, num);
    }

    double GetMedian()
    {
        if (list.empty())
            return 0.0;
        int n = list.size();
        if (list.size() % 2 == 0)
        {
            return (list[n / 2] + list[n / 2 - 1]) / 2.0;
        }
        else
        {
            return (double)list[n / 2];
        }
    }
};